// 最小生成树 Prim 算法实现，输出详细过程
function prim(graph) {
    const n = graph.length; // 图的顶点数量
    const visited = new Array(n).fill(false); // 标记顶点是否已被访问
    const minEdge = new Array(n).fill(Infinity); // 记录当前最小边权值
    const parent = new Array(n).fill(-1); // 记录最小生成树的父节点
    let totalWeight = 0; // 最小生成树的总权值
    const mstEdges = []; // 存储最小生成树的边

    // 从第一个顶点开始
    minEdge[0] = 0; // 起点到自身的权值为 0

    for (let i = 0; i < n; i++) {
        let u = -1, minWeight = Infinity;

        // 找到当前未访问顶点中，权值最小的顶点
        for (let j = 0; j < n; j++) {
            if (!visited[j] && minEdge[j] < minWeight) {
                u = j;
                minWeight = minEdge[j];
            }
        }

        if (u === -1) break; // 如果没有找到有效顶点，退出循环

        visited[u] = true; // 标记当前顶点为已访问
        totalWeight += minWeight; // 累加权值到总权值
        console.log(`选择顶点 ${u}，加入生成树，总权值为 ${totalWeight}`);

        // 更新与当前顶点相邻的未访问顶点的最小边权值
        for (let v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] !== 0 && graph[u][v] < minEdge[v]) {
                minEdge[v] = graph[u][v]; // 更新顶点 v 的最小边权值
                parent[v] = u; // 更新顶点 v 的父节点
            }
        }
    }

    // 输出最小生成树的边
    for (let i = 1; i < n; i++) {
        if (parent[i] !== -1) {
            mstEdges.push([parent[i], i, graph[parent[i]][i]]);
        }
    }

    console.log("\n最小生成树的边集：");
    mstEdges.forEach(edge => {
        console.log(`边: ${edge[0]} - ${edge[1]}, 权值: ${edge[2]}`);
    });

    return totalWeight; // 返回最小生成树的总权值
}

// 测试代码
// 示例图的邻接矩阵（7 个顶点，0 表示无边）
const graph = [
    [0, 2, 0, 6, 0, 0, 0],
    [2, 0, 3, 8, 5, 0, 0],
    [0, 3, 0, 0, 7, 0, 4],
    [6, 8, 0, 0, 9, 0, 0],
    [0, 5, 7, 9, 0, 2, 0],
    [0, 0, 0, 0, 2, 0, 1],
    [0, 0, 4, 0, 0, 1, 0]
];

console.log("最小生成树的总权值:", prim(graph)); // 输出最小生成树的总权值
